//304 Range Sum Query 2D
/*
设计一个数据结构，使得其能够快速查询给定矩阵中，任意两个位置包围的长方形中所有数
字的和。

输入输出样例
	以下是数据结构的调用样例。其中 sumRegion 函数的四个输入分别是第一个点的横、纵坐标，
和第二个点的横、纵坐标
vector<int> matrix{{3,0,1,4,2},
{5,6,3,2,1},
{1,2,0,1,5},
{4,1,0,1,7},
{1,0,3,0,5}
};
NumMatrix num_matrix = new NumMatrix(matrix);
num_matrix.sumRegion(2,1,4,3); // Result = 8.
num_matrix.sumRegion(1,1,2,2); // Result = 11.
*/
class NumMatrix {
	vector<vector<int>> integral;
public:
	NumMatrix(vector<vector<int>> matrix) {
		int m = matrix.size(), n = m > 0 ? matrix[0].size() : 0;
		integral = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				integral[i][j] = matrix[i - 1][j - 1] + integral[i - 1][j] +
					integral[i][j - 1] - integral[i - 1][j - 1];
			}
		}
	}
	int sumRegion(int row1, int col1, int row2, int col2) {
		return integral[row2 + 1][col2 + 1] - integral[row2 + 1][col1] -
			integral[row1][col2 + 1] + integral[row1][col1];
	}
};
